package week_03;

public class BuildTree {
    private int[] preorder;
    private int[] inorder;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder=preorder;
        this.inorder=inorder;
        return clac(0,preorder.length-1,0,inorder.length-1);

    }

    public TreeNode clac(int l1,int r1,int l2,int r2){
        //终止条件
        if(l1>r1) return null;
        // root 点位置,生成root节点
        TreeNode root=new TreeNode(preorder[l1]);
        //在中序中找到root 位置，在区间内分出左树，右树位置
        int mid=l2;
        while(inorder[mid]!=preorder[l1]){
            mid++;
        }
        //递归左树
        root.left= clac(l1+1,l1+mid-l2,l2,mid-1);
        //递归右树
        root.right=clac(l1+mid-l2+1,r1,mid+1,r2);
        return root;
    }


}
